package com.zang.dp;

/**
 * @author ZVerify
 * @since 2022/11/24 09:43
 * @see <a href="https://leetcode.cn/problems/climbing-stairs/">...</a>
 **/
public class 爬楼梯 {
    /**
     * 1. 确认dp含义，dp[i] = 到达第i阶楼梯有多少种方法
     * 2. 递推公式首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
     * 还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
     * dp[i] = dp[i - 1] + dp[i - 2]
     * 3. 初始化
     * 4. 遍历方向
     * 5 举例
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n==1) return 1;
        int[] dp = new int[n + 1];

        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[n];

    }
}
